package com.onpositive.nlp.inflector;


public class StringLevenshteinDisstanceComputer {
	
	private static StringLevenshteinDisstanceComputer instance = new StringLevenshteinDisstanceComputer() ;
	
	public static int computeDisstance( String str1, String str2 )
	{
		return instance.doComputeDisstance(str1, str2) ;
	}
	public static int computeSmartDisstance( String str1, String str2 )
	{
		return instance.doComputeSmartDisstance(str1, str2) ;
	}
	
	private int doComputeDisstance( String str1 , String str2 )
	{
		int l1 = str1.length() ; 
		int l2 = str2.length() ;
		
		int[][] arr = new int[ l1+1 ][ l2+1 ] ;
		
		for( int i = 0 ; i < l1 ; i++ )
			arr[i][0] = i ;
		
		for( int j = 0 ; j < l2 ; j++ )
			arr[0][j] = j ;
		
		for( int i = 1 ; i < l1+1 ; i++ )
			for( int j = 1 ; j < l2+1 ; j++ )
			{
				if( str1.charAt(i-1) == str2.charAt(j-1) )
					arr[i][j] = arr[i-1][j-1] ;
				else
					arr[i][j] = Math.min( Math.min( arr[i][j-1], arr[i-1][j] ), arr[i-1][j-1] ) + 1 ;
			}
		
		return arr[l1][l2] ;
	}
	
	private int doComputeSmartDisstance( String str1 , String str2 )
	{
		int l1 = str1.length() ; 
		int l2 = str2.length() ;
		
		int[][] arr = new int[ l1+1 ][ l2+1 ] ;
		int[][] weight = new int[ l1+1 ][ l2+1 ] ;
		
		initWeights( weight, l1, l2 ) ;
		
		for( int i = 0 ; i < l1 ; i++ )
			arr[i][0] = i ;		
		
		for( int j = 0 ; j < l2 ; j++ )
			arr[0][j] = j ;
		
		
		
		
		for( int i = 1 ; i < l1+1 ; i++ )
			for( int j = 1 ; j < l2+1 ; j++ )
			{
				if( str1.charAt(i-1) == str2.charAt(j-1) ){
					arr[i][j] = arr[i-1][j-1] ;
					int pW = weight[i-1][j-1] ;
					weight[i][j] = weight[i-1][j-1] ;

				}
				else{
					boolean equalErrorsCount = arr[i][j-1] == arr[i-1][j] ;
					if( arr[i][j-1] < arr[i-1][j] || ( equalErrorsCount && weight[i][j-1] < weight[i-1][j] ) )
					{

						equalErrorsCount = arr[i-1][j-1] == arr[i][j-1] ;
						if( arr[i-1][j-1] < arr[i][j-1] || ( equalErrorsCount && weight[i-1][j-1] < weight[i][j-1] ) )
						{
							int pW = weight[i-1][j-1] ;
							int wi = weight[i][0] ;
							int wj = weight[0][j] ;
							arr[i][j] = arr[i-1][j-1] ;
							weight[i][j] = weight[i-1][j-1] + weight[i][0] + weight[0][j] ;							
						}
						else{
							int pW = weight[i][j-1] ;
							int wi = weight[i][0] ;
							int wj = weight[0][j-1] ;
							arr[i][j] = arr[i][j-1] ;
							weight[i][j] = weight[i][j-1] + weight[i][0] + weight[0][j-1] ;
						}
					}
					else{
						equalErrorsCount = arr[i-1][j-1] == arr[i-1][j] ;
						if( arr[i-1][j-1] < arr[i-1][j] || ( equalErrorsCount && weight[i-1][j-1] < weight[i-1][j] ) )
						{
							int pW = weight[i-1][j-1] ;
							int wi = weight[i][0] ;
							int wj = weight[0][j] ;
							arr[i][j] = arr[i-1][j-1] ;
							weight[i][j] = weight[i-1][j-1] + weight[i][0] + weight[0][j] ;
						}
						else{
							int pW = weight[i-1][j] ;
							int wi = weight[i-1][0] ;
							int wj = weight[0][j] ;
							arr[i][j] = arr[i-1][j] ;
							weight[i][j] = weight[i-1][j] + weight[i-1][0] + weight[0][j] ;							
						}

					}
				}
			}		
		
		return weight[l1][l2] ;
	}
	private void initWeights(int[][] weight, int l1, int l2)
	{
		int[] limits1 = initLimits(l1);
		int rootErrVal1 =  5 + ( 10 > l1 ? 10-l1 : 0 ) ;
		
		for( int i = limits1[0] ; i < limits1[1] ; i++ )
			weight[i][0] = rootErrVal1 ;
		
		double step1 = ((double)rootErrVal1 - 1.0) / ( limits1[2]-limits1[1] + 1 ) ;
		for( int i = limits1[1] ; i < limits1[2] ; i++ )
			weight[i][0] = rootErrVal1 - (int)( ( i - limits1[1] + 1 ) * step1 + 0.5) ;
		
		for( int i = limits1[2] ; i < limits1[3] ; i++ )
			weight[i][0] = 1 ;

		
		int[] limits2 = initLimits(l2);
		int rootErrVal2 =  5 + ( 10 > l2 ? 10-l2 : 0 ) ;
		
		for( int j = limits2[0] ; j < limits2[1] ; j++ )
			weight[0][j] = rootErrVal2 ;
		
		double step2 = ((double)rootErrVal2 - 1.0) / ( limits2[2]-limits2[1] + 1 ) ;
		for( int j = limits2[1] ; j < limits2[2] ; j++ )
			weight[0][j] = rootErrVal2 - (int)( ( j - limits2[1] + 1 ) * step2 + 0.5) ;
		
		for( int j = limits2[2] ; j < limits2[3] ; j++ )
			weight[0][j] = 1 ;
	}
	private int[] initLimits(int l) 
	{
		int[] limits = new int[4] ;  
		int prefix  = (int)( l * 0.4 +1 + 0.5 ) ;
		int postfix = (int)( l * 0.3 +1 + 0.5 ) ;
		int mid = l - prefix - postfix ;
		if( mid < 0 )
		{
			mid *= -1 ;
			postfix = mid <= postfix ? postfix - mid : 0 ;					
			mid = 0 ;
			prefix = l - postfix ;		
		}
		limits[0] = 1 ;
		limits[1] = limits[0] + prefix ;
		limits[2] = limits[1] + mid ;
		limits[3] = limits[2] + postfix ;
		
		return limits ;
	}
}
